Serveur d'exploration sur la recherche en informatique en Lorraine

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Distributed algorithms in an ergodic Markovian environment

Identifieur interne : 004C77 ( Main/Exploration ); précédent : 004C76; suivant : 004C78

Distributed algorithms in an ergodic Markovian environment

Auteurs : Francis Comets [France] ; François Delarue [France] ; René Schott [France]

Source :

RBID : ISTEX:A3E5D7773BE939C2AB6A41359D8BF9EAE9E8598B

English descriptors

Abstract

We provide a probabilistic analysis of the d‐dimensional banker algorithm when transition probabilities may depend on time and space. The transition probabilities evolve, as time goes by, along the trajectory of an ergodic Markovian environment, whereas the spatial parameter just acts on long runs. Our model complements the one considered by Guillotin‐Plantard and Schott (Random Struct Algorithm 21 (2002) 3–4, 371–396) where transitions are governed by a dynamical system, and appears as a new (small) step towards more general time and space dependent protocols. Our analysis relies on well‐known techniques from stochastic homogenization theory and investigates the asymptotic behavior of the rescaled algorithm as the total amount of resources available for allocation tends to infinity. In the two‐dimensional setting, we manage to exhibit three different possible regimes for the deadlock time of the limit system. To the best of our knowledge, the way we distinguish these regimes is completely new. We interpret our results in terms of stabilization of the algorithm.© 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007

Url:
DOI: 10.1002/rsa.20154


Affiliations:


Links toward previous steps (curation, corpus...)


Le document en format XML

<record>
<TEI wicri:istexFullTextTei="biblStruct">
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en">Distributed algorithms in an ergodic Markovian environment</title>
<author>
<name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name>
</author>
<author>
<name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name>
</author>
<author>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:A3E5D7773BE939C2AB6A41359D8BF9EAE9E8598B</idno>
<date when="2007" year="2007">2007</date>
<idno type="doi">10.1002/rsa.20154</idno>
<idno type="url">https://api.istex.fr/ark:/67375/WNG-G2VMC03L-D/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">002667</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">002667</idno>
<idno type="wicri:Area/Istex/Curation">002634</idno>
<idno type="wicri:Area/Istex/Checkpoint">001062</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001062</idno>
<idno type="wicri:doubleKey">1042-9832:2007:Comets F:distributed:algorithms:in</idno>
<idno type="wicri:Area/Main/Merge">004E11</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00005841</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00005841</idno>
<idno type="wicri:Area/Hal/Corpus">001C98</idno>
<idno type="wicri:Area/Hal/Curation">001C98</idno>
<idno type="wicri:Area/Hal/Checkpoint">003D77</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">003D77</idno>
<idno type="wicri:doubleKey">1042-9832:2007:Comets F:distributed:algorithms:in</idno>
<idno type="wicri:Area/Main/Merge">005044</idno>
<idno type="wicri:Area/Main/Curation">004C77</idno>
<idno type="wicri:Area/Main/Exploration">004C77</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title level="a" type="main" xml:lang="en">Distributed algorithms in an ergodic Markovian environment</title>
<author>
<name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
<affiliation wicri:level="3">
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire de Probabilités et Modèles Aléatoires, Université Paris 7, UFR de Mathématiques, Case 7012, 2, Place Jussieu, 75251 Paris Cedex 05</wicri:regionArea>
<placeName>
<region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author>
<name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name>
<affiliation wicri:level="3">
<country xml:lang="fr">France</country>
<wicri:regionArea>Laboratoire de Probabilités et Modèles Aléatoires, Université Paris 7, UFR de Mathématiques, Case 7012, 2, Place Jussieu, 75251 Paris Cedex 05</wicri:regionArea>
<placeName>
<region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
<affiliation wicri:level="3">
<country xml:lang="fr">France</country>
<wicri:regionArea>Correspondence address: Laboratoire de Probabilités et Modèles Aléatoires, Université Paris 7, UFR de Mathématiques, Case 7012, 2, Place Jussieu, 75251 Paris Cedex 05</wicri:regionArea>
<placeName>
<region type="region" nuts="2">Île-de-France</region>
<settlement type="city">Paris</settlement>
</placeName>
</affiliation>
</author>
<author>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
<affiliation wicri:level="3">
<country xml:lang="fr">France</country>
<wicri:regionArea>IECN and LORIA, Université Henri Poincaré‐Nancy 1, 54506 Vandoeuvre‐lès‐Nancy</wicri:regionArea>
<placeName>
<region type="region" nuts="2">Grand Est</region>
<region type="old region" nuts="2">Lorraine (région)</region>
<settlement type="city">Vandoeuvre‐lès‐Nancy</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1">
<country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series>
<title level="j" type="main">Random Structures & Algorithms</title>
<title level="j" type="sub">Proceedings from the 12th International Conference “Random Structures and Algorithms”, August 1–5, 2005, Poznan, Poland. Dedicated to Alan Frieze on the occasion of his 60th birthday</title>
<title level="j" type="alt">RANDOM STRUCTURES AND ALGORITHMS</title>
<idno type="ISSN">1042-9832</idno>
<idno type="eISSN">1098-2418</idno>
<imprint>
<biblScope unit="vol">30</biblScope>
<biblScope unit="issue">1‐2</biblScope>
<biblScope unit="page" from="131">131</biblScope>
<biblScope unit="page" to="167">167</biblScope>
<biblScope unit="page-count">37</biblScope>
<publisher>Wiley Subscription Services, Inc., A Wiley Company</publisher>
<pubPlace>Hoboken</pubPlace>
<date type="published" when="2007-01">2007-01</date>
</imprint>
<idno type="ISSN">1042-9832</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt>
<idno type="ISSN">1042-9832</idno>
</seriesStmt>
</fileDesc>
<profileDesc>
<textClass>
<keywords scheme="Teeft" xml:lang="en">
<term>Absorption area</term>
<term>Algorithm</term>
<term>Appl math</term>
<term>Asymptotic</term>
<term>Asymptotic behavior</term>
<term>Banker algorithm</term>
<term>Bessel process</term>
<term>Border line</term>
<term>Boundary conditions</term>
<term>Bracket</term>
<term>Brownian</term>
<term>Brownian motion</term>
<term>Calibration procedure</term>
<term>Cambridge university press</term>
<term>Canonical basis</term>
<term>Central limit theorem</term>
<term>Central limit theorems</term>
<term>Colliding stacks</term>
<term>Comet</term>
<term>Complete review</term>
<term>Constant matrix</term>
<term>Continuous function</term>
<term>Converges</term>
<term>Covariance matrix</term>
<term>Current state</term>
<term>Deadlock phenomenon</term>
<term>Deadlock time</term>
<term>Deadlock zone</term>
<term>Delarue</term>
<term>Dht1</term>
<term>Dht2</term>
<term>Differential form</term>
<term>Diffusion matrix</term>
<term>Diffusion process</term>
<term>Dkt1</term>
<term>Dkt1 dkt2</term>
<term>Dkt2</term>
<term>Doeblin condition</term>
<term>Drift increment</term>
<term>Dynamical system</term>
<term>Elliptic</term>
<term>Ergodic</term>
<term>Ergodic markovian environment</term>
<term>Ergodic theorem</term>
<term>Exhaustion</term>
<term>First step</term>
<term>Formula yields</term>
<term>High probability</term>
<term>Homogenization</term>
<term>Homogenization theory</term>
<term>Identity matrix</term>
<term>Initial condition</term>
<term>Invariant measure</term>
<term>Jacod</term>
<term>Lemma</term>
<term>Likely displacements</term>
<term>Likely steps</term>
<term>Limit form</term>
<term>Limit process</term>
<term>Limit system</term>
<term>Limit theorem</term>
<term>Lipschitz</term>
<term>Lipschitz continuity</term>
<term>Lowest eigenvalue</term>
<term>Lyapunov function</term>
<term>Maier</term>
<term>Main axis</term>
<term>Main eigenvector</term>
<term>Main results</term>
<term>Markov</term>
<term>Markov chain</term>
<term>Markov chains</term>
<term>Markov processes</term>
<term>Markovian</term>
<term>Martingale</term>
<term>Martingale part</term>
<term>Martingale parts</term>
<term>Martingale problem</term>
<term>Matrix</term>
<term>Measurable function</term>
<term>Nite</term>
<term>Other words</term>
<term>Pardoux</term>
<term>Periodic structures</term>
<term>Poisson equations</term>
<term>Practical applications</term>
<term>Probab theory</term>
<term>Probabilistic</term>
<term>Probabilistic analysis</term>
<term>Process converges</term>
<term>Random environment</term>
<term>Random struct algorithms</term>
<term>Random structures</term>
<term>Rescaled</term>
<term>Right hand side</term>
<term>Same argument</term>
<term>Same property</term>
<term>Scalar product</term>
<term>Schott</term>
<term>Second eigenvalue</term>
<term>Second inequality</term>
<term>Second picture</term>
<term>Second point</term>
<term>Second step</term>
<term>Second term</term>
<term>Semimartingale form</term>
<term>Shiryaev</term>
<term>Similar argument</term>
<term>Skorokhod</term>
<term>Skorokhod topology</term>
<term>Small adjustment</term>
<term>Space dependency</term>
<term>Square integrable martingale</term>
<term>State space</term>
<term>Stochastic</term>
<term>Stochastic homogenization</term>
<term>Stochastic homogenization theory</term>
<term>Supremum norm</term>
<term>Third step</term>
<term>Tightness properties</term>
<term>Total amount</term>
<term>Trajectory</term>
<term>Transience properties</term>
<term>Transition kernel</term>
<term>Transition matrix</term>
<term>Transition probabilities</term>
<term>Unique solution</term>
<term>Whole proof</term>
<term>Wiley periodicals</term>
</keywords>
<keywords scheme="mix" xml:lang="en">
<term>distributed algorithms</term>
<term>random environment</term>
<term>reflected diffusion</term>
<term>stochastic homogenization</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">We provide a probabilistic analysis of the d‐dimensional banker algorithm when transition probabilities may depend on time and space. The transition probabilities evolve, as time goes by, along the trajectory of an ergodic Markovian environment, whereas the spatial parameter just acts on long runs. Our model complements the one considered by Guillotin‐Plantard and Schott (Random Struct Algorithm 21 (2002) 3–4, 371–396) where transitions are governed by a dynamical system, and appears as a new (small) step towards more general time and space dependent protocols. Our analysis relies on well‐known techniques from stochastic homogenization theory and investigates the asymptotic behavior of the rescaled algorithm as the total amount of resources available for allocation tends to infinity. In the two‐dimensional setting, we manage to exhibit three different possible regimes for the deadlock time of the limit system. To the best of our knowledge, the way we distinguish these regimes is completely new. We interpret our results in terms of stabilization of the algorithm.© 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007</div>
</front>
</TEI>
<affiliations>
<list>
<country>
<li>France</li>
</country>
<region>
<li>Grand Est</li>
<li>Lorraine (région)</li>
<li>Île-de-France</li>
</region>
<settlement>
<li>Paris</li>
<li>Vandoeuvre‐lès‐Nancy</li>
</settlement>
</list>
<tree>
<country name="France">
<noRegion>
<name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name>
</noRegion>
<name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name>
<name sortKey="Comets, Francis" sort="Comets, Francis" uniqKey="Comets F" first="Francis" last="Comets">Francis Comets</name>
<name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name>
<name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name>
<name sortKey="Delarue, Francois" sort="Delarue, Francois" uniqKey="Delarue F" first="François" last="Delarue">François Delarue</name>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
<name sortKey="Schott, Rene" sort="Schott, Rene" uniqKey="Schott R" first="René" last="Schott">René Schott</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 004C77 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 004C77 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     ISTEX:A3E5D7773BE939C2AB6A41359D8BF9EAE9E8598B
   |texte=   Distributed algorithms in an ergodic Markovian environment
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022